1. Field of the Invention
The invention relates to a data processing system utilizing an oblivious RAM that enables high speed transmission between substantially free-standing heterogeneous, geographically remote data processing equipment.
2. Description of the Related Art
The purpose of using a high performance computer network is to access data stored on remote machines as if it were stored locally. In particular, the time needed to access remote data should be nearly the same as the main memory (local data) access time. The two main obstacles that have historically confronted computer engineers are (1) the difficulty of fast data transmission, and (2) geographic separation. These obstacles must be simultaneously overcome to allow remote memory to perform like main memory. Local and remote data are accessed in two basic ways. The data may be (1) read from memory or (2) written to memory. In the hardware of the prior art a remote data access (read/write) is typically a two stage process starting with the operation initialization signal (or set of signals) and finishing with an operation completion signal set. Between these two stages, the prior art requires that the initialization signals travel from the source to the target and the completion signals return from the target to the source. Since read and write operations are indivisible (atomic processor operations that cannot be partially executed), the machine is not available for any other processing while the signals move back and forth. Both electrical and lightwave signals move very rapidly, even over relatively long distances. But, such transmission speeds (necessarily bounded by the speed of light) are considered slow compared to the transmission speeds needed by both current conventional and future high-performance data processing equipment. For example, in one nanosecond, the fastest signal possible, light, can move no more than one foot. Processors that can execute one instruction every 30 nanoseconds are relatively common. For any such processor to execute a stream of instructions, without interruption and using the prior art, all the data to be operated on must be within 30 feet of the processor. With prior art technologies, as processors get faster their data sources will have to be closer to the processor. Soon, the physical volume of the data source itself will limit the speed of the nearby processor. In summary, prior art computer networks either rapidly transmit data over short distances or slowly transmit data over long distances, but they cannot do both.
U.S. Pat. No. 3,771,137 discloses a design of a monolithic multiprocessor unit. This design insures that the local memories of the respective communicating computers are always coherent. Hence, an update of a single shared location requires waiting for either cache invalidation signals or cache update signal to travel to all the other processors. The disclosure involves systems expected to run processing elements separated by no more than a few feet. Signal propagation delay attendant with widely separated computers is not addressed in this disclosure. Nor does this disclosure discuss the problems associated with the use of heterogeneous computers, or the use of available wiring or reliable distributed performance.
U.S. Pat. No. 4,212,057 discloses a shared memory multi-processor system. The disclosure provides for the use of a single memory residing on a single machine that is shared between a multiplicity of processors. The design requires that the single shared memory send wait signals back to the communicating processor. Since memory physically resides in only one machine, this design cannot connect communicating processors with even modest lengths of cable without making provisions for signal propagation delay. When a remote access is in progress a wait signal is sent from the remote processor to the local processor. On a remote access, the wait signal performs a complex two-fold role. On the local machine, the wait signal informs the bus that although the current operation is slower than normal, the hardware is still operating correctly. On the remote machine, the wait signal is used to ensure serialized access to the memory. In other words, wait signals prevent collision between memory accesses that could result in lost or incorrect data. During the wait signal time, the local processor remains idle. While computers using a shared memory will, in general, communicate faster than machines not using shared memory, the speed of transmission of each datum is still proportional to the signal propagation delay due to the introduction of wait states. In some cases, high latency data transmission speeds may be slowed, relative to local memory access, by up to a factor of 1000.
U.S. Pat. No. 4,543,627 discloses a computer network that employs intelligent front-end interface processors. The intelligent processing cannot, in general, overcome the physical constraint of signal propagation delay or network latency.
The following U.S. Pat. Nos. are considered of possible general interest to the application: 3,581,291, 4,118,771, 4,181,935, 4,212,057, 4,213,177, 4,215,398, 4,223,380, 4,256,926, 4,371,929, 4,400,775, 4,410,994, 4,414,620, 4,445,174, 4,471,427, 4,503,496, 4,504,902, 4,504,906, 4,577,273, 4,591,977, 4,703,421.